package com.black.cat.algorithm.tree;

/**
 * @description:二叉搜索树 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
 * 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
 * 任意节点的左、右子树也分别为二叉查找树；
 * @version: 1.0
 * @create：2023/3/13 17:00
 * @author：blackcat
 */
public class BinarySearchTree extends AbstractTree {

    private int size = 0;

    public Node insert(int e) {

        //如果不存在root,说明是首节点，新建返回即可
        if (root == null) {
            root = new Node(e, null, null, null);
            size++;
            return root;
        }

        //查询新增节点的父节点
        Node parent = root;
        Node search = root;
        while (search != null) {
            parent = search;
            if (search.getValue() > e) {
                search = search.left;
            } else {
                search = search.right;
            }
        }

        //创建新节点
        Node newNode = new Node(e, parent, null, null);

        //比较新节点和父节点的值大小，确定是左子节点还是右子节点
        if (e > parent.getValue()) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
        return newNode;
    }

    public Node search(int e) {
        Node node = root;
        while (node != null && node.value != null && node.value != e) {
            if (e < node.value) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return node;
    }

    //删除节点
    public Node delete(int e) {
        Node delNode = search(e);
        if (null == delNode) return null;
        return delete(delNode);
    }

    //删除节点
    protected Node delete(Node delNode) {
        if (delNode == null) return null;
        Node result = null;
        //删除节点只有单个孩子节点
        if (delNode.left == null) {
            result = transplant(delNode, delNode.right);
        } else if (delNode.right == null) {
            result = transplant(delNode, delNode.left);
        } else {
            // 因为删除的节点，有2个孩子节点，这个时候找到这条分支下，最左侧做小的节点。用它来替换删除的节点
            Node miniNode = getMiniNode(delNode.right);
            if (miniNode.parent != delNode) {
                // 交换位置，用miniNode右节点，替换miniNode
                transplant(miniNode, miniNode.right);
                // 把miniNode 提升父节点，设置右子树并进行挂链。替代待删节点
                miniNode.right = delNode.right;
                miniNode.right.parent = miniNode;
            }
            // 交换位置，删除节点和miniNode 可打印测试观察；System.out.println(this);
            transplant(delNode, miniNode);
            // 把miniNode 提升到父节点，设置左子树并挂链
            miniNode.left = delNode.left;
            miniNode.left.parent = miniNode;
            result = miniNode;
        }
        size--;
        return result;
    }


    protected Node getMiniNode(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 节点替换
     *
     * @param delNode 删除节点
     * @param addNode 替换节点
     */
    protected Node transplant(Node delNode, Node addNode) {
        if (delNode.parent == null) {
            this.root = addNode;
        }// 判断删除元素是左/右节点
        else if (delNode.parent.left == delNode) {
            delNode.parent.left = addNode;
        } else {
            delNode.parent.right = addNode;
        }
        // 设置父节点
        if (null != addNode) {
            addNode.parent = delNode.parent;
        }
        return addNode;
    }

    public static void main(String[] args) {

        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(32);
        tree.insert(7);
        tree.insert(64);
        tree.insert(63);
        tree.insert(89);
        tree.insert(72);
        tree.insert(94);
        tree.insert(6);
        tree.insert(14);
        tree.insert(18);
        tree.insert(73);

        System.out.println(tree);
        // 删除单节点，只有一个孩子的父节点
        // tree.delete(14);

        // 删除双节点，拥有二个孩子的父节点
        tree.delete(64);
        System.out.println(tree);
    }
}
